import com.sun.org.apache.regexp.internal.RE;

/**
 * @ClassName :   StringArrayCommonLength
 *字符串数组最长公共长度
 * @Description:
 * @Author: cq
 * @CreateDate: 2021/7/1 16:34
 * @Version: 1.0
 */
public class StringArrayCommonLength {

    public static void main(String[] args) {

        System.out.println(dichotomy(new String[]{"leetlds","leet0ejd","leetldsde","leetldfde","leetldgts","leetlejd5h",}));
    }
    /**
     * @Description:横向扫描
     * @Param:
     * @return 
     **/
    public static String lateralScan(String[] strs){
        if (null == strs || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    /**
     * @Description: 返回两个字符串的公共字符串
     * @Param:
     * @return 
     **/
    private static String longestCommonPrefix(String prefix, String str) {
        Integer length = Math.min(prefix.length(), str.length());
        Integer index = 0;
        while (index < length && prefix.charAt(index) == str.charAt(index)) {
            index++;
        }
        return prefix.substring(0, index);
    }

    /**
     * @Description: 纵向扫描
     * @Param:
     * @return 
     **/
    public  static  String portraitScan(String[] strs){
        if (null == strs || strs.length == 0) {
            return "";
        }
        Integer index = 0;
        Integer count = strs.length;
        Integer length = strs[0].length();
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 0; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    /**
     * @Description:分治法
     * @Param:
     * @return 
     **/
    public static String divideConquer(String[] strs){
        if (null == strs || strs.length == 0) {
            return "";
        }else {
            return  longestCommonPrefix(strs,0,strs.length-1);
        }
    }

    /**
     * @Description: 拆分
     * @Param:
     * @return 
     **/
    private static String longestCommonPrefix(String[] strs, int strat, int end) {
        if (strat == end) {
            return strs[strat];
        } else {
            int mid = (end - strat) / 2 + strat;
            String lcpLeft = longestCommonPrefix(strs, strat, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    /**
     * @Description:返回两个字符串的公共字符串
     * @Param:
     * @return 
     **/
    private static String commonPrefix(String lcpLeft, String lcpRight) {
        Integer minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i =0; i<minLength; i++){
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)){
                return  lcpLeft.substring(0,i);
            }
        }
        return lcpLeft.substring(0,minLength);
    }

    /**
     * @Description:二分查找
     * @Param:
     * @return
     **/
    public static String dichotomy(String[] strs){
        if (null == strs || strs.length == 0) {
            return "";
        }
        Integer minLength = Integer.MAX_VALUE;
        for (String str :strs){
            minLength = Math.min(minLength,str.length());
        }
        Integer low =0;
        Integer high = minLength;
        while(low < high){
            Integer mid =(high -low + 1)/2 + low;
            if(isCommonPrefix(strs,mid)){
                low=mid;
            }else {
                high = mid-1;
            }
        }
        
        return strs[0].substring(0,low);
    }

    /**
     * @Description:
     * @Param:
     * @return 
     **/
    private static boolean isCommonPrefix(String[] strs, Integer length) {
        String str = strs[0].substring(0,length);
        int count = strs.length;
        for (int i=1; i<count;i++){
            String str1 = strs[i];
            for (int j =0; j<length; j++){
                if(str.charAt(j) != str1.charAt(j)){
                    return false;
                }
            }
        }
        return true;
    }

}
